| 翻訳と辞書 |
| shallow minor ： ウィキペディア英語版 |
shallow minor
In graph theory, a shallow minor or limited-depth minor is a restricted form of a graph minor in which the subgraphs that are contracted to form the minor have small diameter. Shallow minors were introduced by , who attributed their invention to Charles E. Leiserson and Sivan Toledo.〔
==Definition==
One way of defining a minor of an undirected graph ''G'' is by specifying a subgraph ''H'' of ''G'', and a collection of disjoint subsets ''S''''i'' of the vertices of ''G'', each of which forms a connected induced subgraph ''H''''i'' of ''H''. The minor has a vertex ''v''''i'' for each subset ''S''''i'', and an edge
''v''''i''''v''''j'' whenever there exists an edge from ''S''''i'' to ''S''''j'' that belongs to ''H''.
In this formulation, a ''d''-shallow minor (alternatively called a shallow minor of depth ''d'') is a minor that can be defined in such a way that each of the subgraphs ''H''''i'' has ''radius'' at most ''d'', meaning that it contains a central vertex ''c''''i'' that is within distance ''d'' of all the other vertices of ''H''''i''. Note that this distance is measured by hop count in ''H''''i'', and because of that it may be larger than the distance in ''G''.〔, Section 4.2 "Shallow Minors", pp. 62–65.〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「shallow minor」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|